package com.peng.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * MinimumTotal
 * 剑指 Offer II 100. 三角形中最小路径之和
 * https://leetcode.cn/problems/IlPe0q/
 *
 * @author: lupeng6
 * @create: 2023/2/23 13:11
 */
public class MinimumTotal {

    //    [[2],[3,4],[6,5,7],[4,1,8,3]]
    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(new Integer[]{2}));
        triangle.add(Arrays.asList(new Integer[]{3, 4}));
        triangle.add(Arrays.asList(new Integer[]{6, 5, 7}));
        triangle.add(Arrays.asList(new Integer[]{4, 1, 8, 3}));
        System.out.println(new MinimumTotal().minimumTotal(triangle));
    }

    private int ans = Integer.MAX_VALUE;

    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        backtrack(triangle, 0, 0, 0);
        return ans;
    }

    void backtrack(List<List<Integer>> triangle, int index1, int index2, int sum) {
        sum += triangle.get(index1).get(index2);
        if (index1 == triangle.size()) {
            this.ans = Math.max(sum, ans);
            return;
        }
        if (index2 > 0) {
            backtrack(triangle, index1 + 1, index2 - 1, sum + triangle.get(index1).get(index2));
        }
        if (index2 < triangle.get(index1).size() - 1) {
            backtrack(triangle, index1 + 1, index2 + 1, sum + triangle.get(index1).get(index2));
        }
    }
}
